#include "common.h"

//—————————— 存放答案的动态数组 ————————————————————————————
struct vector_char {
	char** _array;
	size_t _lastIndex;
	size_t _capacity;
};

/* 初始化 存放答案的动态数字 */
struct vector_char* initial()
{
	struct vector_char* vec = malloc(sizeof(struct vector_char));
	vec->_array = calloc(8, sizeof(char*));
	vec->_capacity = 8;
	vec->_lastIndex = 0;
	return vec;
}

/* 在动态数组里存放元素 */
void put_back(struct vector_char* vec, char* string)
{
	/* 容量不够时，扩容 */
	if (vec->_lastIndex == vec->_capacity) {
		vec->_capacity += vec->_capacity >> 1;
		vec->_array = realloc(vec->_array, vec->_capacity * sizeof(char*));
	}
	vec->_array[vec->_lastIndex++] = string;
}

//————————— 动态字符串 ——————————————
struct vector_string {
	char* _str;
	size_t _lastIndex;
	size_t _capacity;
};

//————————— 函数原型 ———————————————
char** addOperators(char* num, int target, int* returnSize);

void dfs(int u, long prev, long cur, struct vector_string s);

//————————— 测试用例 ———————————————
int main()
{
	char str_num[10];
	scanf("%s", str_num);
	int target;
	scanf("%d", &target);
	int* returnSize = malloc(sizeof(int));
	char** res = addOperators(str_num, target, returnSize);
	for (int i = 0, len = *returnSize; i < len; i++)
		printf("%s\n", res[i]);
	return 0;
}

//————————— leetcode模板 — 算法入口 ———————
char* str;
int str_len, target_val;
struct vector_char* res;

char** addOperators(char* num, int target, int* returnSize)
{
	str = num;
	str_len = strlen(str);
	target_val = target;
	res = initial();

	char* s_arr = calloc(str_len * 2, sizeof(char));
	struct vector_string s = { s_arr, 0, str_len * 2 };

	dfs(0, 0, 0, s);

	*returnSize = res->_lastIndex;
	return res->_array;
}

//———————— 辅助函数 ———————————————
void dfs(int u, long prev, long cur, struct vector_string s)
{
	if (u == str_len) {
		if (cur == target_val) {
			char* one_res = calloc(s._lastIndex + 1, sizeof(char));
			strcpy(one_res, s._str);
			put_back(res, one_res);
		}
		return;
	}

	for (int i = u; i < str_len; i++) {
		if (i != u && str[u] == '0')
			break;
		char str_long[i - u + 2];
		str_long[i - u + 1] = '\0'; //多谢 yuki姐！！！
		strncpy(str_long, str + u, i - u + 1);
		long next = atol(str_long);

		int next_len = log10(next == 0 ? 1 : next) + 1;
		if (u == 0) {
			sprintf(s._str + s._lastIndex, "%ld", next);
			s._lastIndex += next_len;
			dfs(i + 1, next, next, s);
			s._lastIndex -= next_len;
		} else {
			sprintf(s._str + s._lastIndex, "+%ld", next);
			s._lastIndex += next_len + 1;
			dfs(i + 1, next, cur + next, s);
			s._lastIndex -= next_len + 1;

			sprintf(s._str + s._lastIndex, "-%ld", next);
			s._lastIndex += next_len + 1;
			dfs(i + 1, -next, cur - next, s);
			s._lastIndex -= next_len + 1;

			long x = prev * next;
			sprintf(s._str + s._lastIndex, "*%ld", next);
			s._lastIndex += next_len + 1;
			dfs(i + 1, x, cur - prev + x, s);
			s._lastIndex -= next_len + 1;
		}
	}
}
